/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-11-15
 * Time: 10:16
 */
public class TSP {
    public int solveTSP(int[][] distance) {
        int n = distance.length; // 城市数量
        if (n == 0) return 0;
        int fullMask = (1 << n) - 1; // 所有城市都被访问的状态（二进制全1）
        int INF = Integer.MAX_VALUE / 2; // 避免加法溢出

        // dp[mask][u]：访问mask中的城市，最终在u的最短距离
        int[][] dp = new int[1 << n][n];
        // 初始化：所有状态设为无穷大
        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = INF;
            }
        }
        // 起点：从城市0出发，只访问城市0，距离为0
        dp[1 << 0][0] = 0;

        // 遍历所有状态
        for (int mask = 0; mask < (1 << n); mask++) {
            // 遍历当前状态下可能的所在城市u
            for (int u = 0; u < n; u++) {
                // 如果mask中包含u，且当前状态距离有效
                if ((mask & (1 << u)) != 0 && dp[mask][u] != INF) {
                    // 尝试访问未去过的城市v
                    for (int v = 0; v < n; v++) {
                        // 如果v未被访问（mask中不含v）
                        if ((mask & (1 << v)) == 0) {
                            int newMask = mask | (1 << v); // 更新状态（加入v）
                            // 更新到v的最短距离
                            dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + distance[u][v]);
                        }
                    }
                }
            }
        }

        // 计算最终结果：所有城市都访问后，从u回到起点0的最短距离
        int result = INF;
        for (int u = 0; u < n; u++) {
            result = Math.min(result, dp[fullMask][u] + distance[u][0]);
        }
        return result;
    }

    public static void main(String[] args) {
        // 示例：4个城市的距离矩阵（distance[i][j]是城市i到j的距离）
        int[][] distance = {
                {0, 10, 15, 20},
                {10, 0, 35, 25},
                {15, 35, 0, 30},
                {20, 25, 30, 0}
        };

        TSP tsp = new TSP();
        int minDistance = tsp.solveTSP(distance);
        System.out.println("最短旅行距离：" + minDistance); // 输出 80（0→1→3→2→0）
    }
}
